/**
 * Viterbi.java created by zhangzhidong 
 * at 下午10:17:58 2015年10月23日
 */
package algorithm.viterbi;

/**
 * @author zhangzhidong
 *
 */
public class Viterbi {
	
		public static void main(String args[]){
			Homework gar = new Homework();
			double receive [] = gar.receive(System.out);
			new Viterbi().viterbi(Viterbi.H, receive);
		}
		static double H [][] = Homework.H;//原来的信道矩阵
		static int transition[][] = {
			{0,1},
			{2,3},
			{4,5},
			{6,7},
			{0,1},
			{2,3},
			{4,5},
			{6,7}
			
		};
		public double []	viterbi(double H[][],double []input){
			

			
			
			
//			double A[][] = new double [4][input.length];
//			int path[] []= new int [4][input.length];
//			//0 -> -2,-2 ;	1->-2,2;	2->2,-2;	3->2,2
//			double states[][] = new double[][]{
//				{-2,-2},
//				{-2,2},
//				{2,-2},
//				{2,2}
//			};
//			
//			double [] distance = new double [4];
//			for(int i=0;i<distance.length;i++){
//				double ex[] = extend(states[i], 10);
//				double r1[] =	Homework.matrixMultply(H, ex);
//				distance[i] = Homework.distance(input, r1,2);
//				A[1][i] = distance[i];
//				path[1][i] = i;
//			}
//			for(int x=2;x<A[0].length;x++){
//				
//			}
			
			
			
//			A[0][0] = -2.0;A[0][1] = -2.0;
//			A[1][0] = -2.0;A[1][1] = 2.0;
//			A[2][0] = 2.0;A[2][1] = -2.0;
//			A[3][0] = 2.0;A[3][1] = 2.0;
//			for(int i=2;i<input.length;i++){
//				for(int k=0;k<4;k++){
//					A[k][i]=-2.0;
//				}
//			}
//			double distance[] = new double [A.length];
//			double minValue =Double.MAX_VALUE;
//			int minIndex = -1;
//			for(int m =0;m<distance.length;m++){
//				
//				distance[m] = Homework.distance(input, A[m]);
//				if(distance[m]<minValue){
//					minValue = distance[m];
//					minIndex = m;
//				}
//			}
//			path[0] = (int)A[minIndex][0];
			
			return null;
		}
		public static double [] extend(double []input,int k){
			double result [] = new double [k];
			int z=0;
			for(;z<input.length;z++){
				result[z]=input[z];
			}
			while(z<k){
				result[z++] = -2;
			}
			return result;
		}
		public  static void test(){
			Homework gar = new Homework();
			double receive [] = gar.receive(System.out);
			
			double result[] = Homework.matrixMultply(H,new double []{2,-2,-2,-2,-2,-2,-2,-2,-2,-2} );
			double result2[] = Homework.matrixMultply(H, new double []{2,2,-2,-2,-2,-2,-2,-2,-2,-2});
			double result3[] = Homework.matrixMultply(H, new double []{-2,2,-2,-2,-2,-2,-2,-2,-2,-2});
			double result4[] = Homework.matrixMultply(H, new double []{-2,-2,-2,-2,-2,-2,-2,-2,-2,-2});
			double d1 = Homework.distance(result,receive);
			double d2 = Homework.distance(result2,receive );
			double d3 = Homework.distance(result3,receive );
			double d4 = Homework.distance(result4,receive );
			System.out.println();
		}
	    /**
	     * 
	     * @param obs 观测序列
	     * @param states 隐状态
	     * @param start_p 初始概率（隐状态）
	     * @param trans_p 转移概率（隐状态）
	     * @param emit_p 发射概率 （隐状态表现为显状态的概率）
	     * @return 最可能的序列
	     */
	    public static int[] compute(int[] obs, int[] states, double[] start_p, double[][] trans_p, double[][] emit_p)
	    {
	        double[][] V = new double[obs.length][states.length];
	        int[][] path = new int[states.length][obs.length];
	 
	        for (int y : states)
	        {
	            V[0][y] = start_p[y] * emit_p[y][obs[0]];
	            path[y][0] = y;
	        }
	 
	        for (int t = 1; t < obs.length; ++t)
	        {
	            int[][] newpath = new int[states.length][obs.length];
	 
	            for (int y : states)
	            {
	                double prob = -1;
	                int state;
	                for (int y0 : states)
	                {
	                    double nprob = V[t - 1][y0] * trans_p[y0][y] * emit_p[y][obs[t]];
	                    if (nprob > prob)
	                    {
	                        prob = nprob;
	                        state = y0;
	                        // 记录最大概率
	                        V[t][y] = prob;
	                        // 记录路径
	                        System.arraycopy(path[state], 0, newpath[y], 0, t);
	                        newpath[y][t] = y;
	                    }
	                }
	            }
	 
	            path = newpath;
	        }
	 
	        double prob = -1;
	        int state = 0;
	        for (int y : states)
	        {
	            if (V[obs.length - 1][y] > prob)
	            {
	                prob = V[obs.length - 1][y];
	                state = y;
	            }
	        }
	 
	        return path[state];
	    }
	}
